Módulo Redes Sociales: Sesión 3

Departamento de Estadística

Universidad Nacional de Colombia, Sede Bogotá

Equipo de trabajo

Docente del módulo

Monitor del módulo

Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):

Code 
# cambia idioma de la consola de R a español:
Sys.setenv(LANG="es")
# usar 2 cifras significativas y tiende a evitar 
# notación científica (ver ayuda de función: `options`): 
options(digits = 2, scipen = 999) 
# cargar librerías: 
if(!require(igraph)){
  install.packages("igraph"); library(igraph)}
if(!require(sand)){
  install.packages("sand"); library(sand)}

Grafos y subgrafos

Grafos

Un grafo G = (V, E) es una estructura que consiste de un conjunto de vértices (nodos) V y de un conjunto de aristas (enlaces) E, donde los elementos de E son parejas de la forma e=\{u,v\}, con u,v\in V.

Subgrafos

Un grafo G'=(V',E') es un subgrafo de G=(V,E) si V'\subset V y E'\subset E.

Isomorfismo

Dos grafos que son equivalentes estructuralmente (a pesar de las etiquetas de los vértices) se denominan isomorfos.

Dos grafos G_1 = (V_1, E_1) y G_2 = (V_2, E_2) son isomorfos, lo que se escribe G_1 \equiv G_2, si existe una biyección \varphi:V_1\longrightarrow V_2 tal que \{u,v\}\in E_1 si y solo si \{\varphi(u),\varphi(v)\}\in E_2.

Ejemplo

Si G_1 \equiv G_2, entonces |V_1| = |V_2| y |E_1| = |E_2|.

Si |V_1| \neq |V_2| o |E_1| \neq |E_2|, entonces G_1 \not\equiv G_2.

Si G_1 \equiv G_2 y \{u,v\}\notin E_1, entonces \{\varphi(u),\varphi(v)\}\notin E_2.

Ejercicio

¿G_1 y G_2 son isomorfos?

Ejemplo Práctico

Creación grafos

suppressMessages(suppressWarnings(library(igraph)))

g1 <- graph_from_literal(0-1, 1-2, 2-3, 3-4, 4-0)
g2 <- graph_from_literal(a-c, a-d, b-d, b-e, c-e)

Son isomorfos?

# 'method'
# auto: Selecciona el mejor procedimiento
# direct: Si el grafo tiene tres o cuatro vértices
# vf2: Si el grafo es dirigido
# bliss: En cualquier otro caso

isomorphic(g1, g2, method = "auto")
[1] TRUE

Visualización

# visualización
set.seed(123)
par(mfrow = c(1,2))
plot(g1, vertex.size = 15, main = "Grafo 1")
plot(g2, vertex.size = 15, main = "Grafo 2")

Plan de formación DNI-UNAL 2024 - Perfil 1